package jdt.geom;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

import jdt.utils.JdtUtil;

import com.google.common.collect.ImmutableSet;

public class Triangle {

	/* --- Data members --- */

	/** The points of the triangle */
	private Point a;
	private Point b;
	private Point c;

	/** All the edges of this triangle */
	private ImmutableSet<Edge> edgeSet;
	
	/** All the edges of this triangle in clockwize order */
	private ImmutableSet<DirectedEdge> directedEdgeSet;

	/** All the vertices of this triangle */
	private ImmutableSet<Point> verticesSet;

	/** The commonCirlce of the triangulation */
	private Circle commonCircle;

	/* --- Ctors. --- */

	/**
	 * Construct a triangle using it's three points
	 * 
	 * @param a
	 *            the first point
	 * @param b
	 *            the second Point
	 * @param c
	 *            the third Point
	 */
	public Triangle(Point a, Point b, Point c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}

	/**
	 * Construct a triangle using a list of points
	 * 
	 * @param points
	 *            A list of three points
	 * @throws GeometryException
	 *             if the list's size in not 3
	 */
	public Triangle(List<Point> points) throws GeometryException {
		if (points.size() == 3) {
			a = points.get(0);
			b = points.get(1);
			c = points.get(2);
		} else {
			throw new GeometryException(
					"points must contain excatly three points");
		}
	}
	
	/**
	 * Create a triangle using an edge and a point
	 * @param e The edge to use
	 * @param p The point to use
	 */
	public Triangle(Edge e, Point p){
		this(e.getPoints().get(0), e.getPoints().get(1), p);
	}

	/* --- Public Methods --- */

	/**
	 * Returns true iff the argument point is inside the triangle.<br>
	 * A point is inside the triangle if it's really inside it, or on one of the
	 * triangle's edgaes.<br>
	 * 
	 * @param p
	 *            the point to check
	 * @return True or false
	 */
	public boolean contains(Point p) {
		PointToTriangleRelation realtion = getRealtion(p);
		return !realtion.equals(PointToTriangleRelation.OUTSIDE);
	}

	/**
	 * Returns the vertex which in not on the edge.<br>
	 * The argument edge must be one of this triangle's edges
	 * 
	 * @param e
	 *            The edge to find the opposite vertex to
	 * @return a {@link Point} (the found vertex)
	 * @throws GeometryException
	 *             if the argument edge is not of this triangle
	 */
	public Point getOppositeVertex(Edge e) throws GeometryException {
		if (getEdgeSet().contains(e)) {
			List<Point> edgePoints = e.getPoints();
			if (!edgePoints.contains(a)) {
				return a;
			} else if (!edgePoints.contains(b)) {
				return b;
			} else {
				return c;
			}
		} else {
			throw new GeometryException("The edge must be of this triangle");
		}
	}

	/**
	 * If this triangle contains the argument point, splits this triangle to
	 * sub-triangles.
	 * 
	 * @param p
	 *            The point to split by
	 * @return the created triangles
	 * @throws GeometryException
	 *             if the point is not inside the triangle
	 */
	public Set<Triangle> split(Point p)
			throws GeometryException {
		Set<Triangle> triangleSet = new HashSet<Triangle>();
		switch (getRealtion(p)) {
		case INSIDE:
			triangleSet.add(new Triangle(a, b, p));
			triangleSet.add(new Triangle(a, c, p));
			triangleSet.add(new Triangle(c, b, p));
			break;
		case ON_AB:
			triangleSet.add(new Triangle(a, c, p));
			triangleSet.add(new Triangle(c, b, p));
			break;
		case ON_AC:
			triangleSet.add(new Triangle(a, b, p));
			triangleSet.add(new Triangle(c, b, p));
			break;
		case ON_BC:
			triangleSet.add(new Triangle(a, b, p));
			triangleSet.add(new Triangle(a, c, p));
			break;
		case OUTSIDE:
			throw new GeometryException("The point is not inside the triangles");
		case VERTEX:
			throw new GeometryException("The point is already in the triangulation: " + p);
		}
		return triangleSet;
	}
	
	/**
	 * Checks if the argument triangle has an overlapping vertex with this
	 * triangle
	 * 
	 * @return True or false
	 */
	public boolean isRelated(Triangle triangle) {
		boolean hasA = triangle.getRealtion(a).equals(
				PointToTriangleRelation.VERTEX);
		boolean hasB = triangle.getRealtion(b).equals(
				PointToTriangleRelation.VERTEX);
		boolean hasC = triangle.getRealtion(c).equals(
				PointToTriangleRelation.VERTEX);
		return hasA || hasB || hasC;
	}

	/**
	 * Check if any of the points of the argument edge are vertices of this
	 * triangle
	 * 
	 * @param edge
	 *            THe edge to check
	 * @return True if at least one point of the edge is a vertex of this
	 *         triangle
	 */
	public boolean isRelated(Edge edge) {
		List<Point> points = edge.getPoints();
		Set<Point> thisVerticesSet = new HashSet<Point>(getVerticesSet());
		return thisVerticesSet.removeAll(points);
	}

	/**
	 * Calculates the circle which all the vertices of this triangle lay on
	 * 
	 * @return the {@link Circle}
	 */
	public synchronized Circle getCircumCircle() {
		if (commonCircle == null) {
			Point center = getCircumCenter();
			commonCircle = new Circle(center, center.distance(a));
		}
		return commonCircle;
	}


	public String toString() {
		return "Triangle " + a + " " + b + " " + c;
	}

	/* --- Equals and HashCode --- */

	/**
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
		final int prime = 31;
		int result1 = prime + ((a == null) ? 0 : a.hashCode());
		int result2 = prime + ((b == null) ? 0 : b.hashCode());
		int result3 = prime + ((c == null) ? 0 : c.hashCode());
		return result1 * result2 * result3;
	}

	/**
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof Triangle))
			return false;

		Triangle other = (Triangle) obj;
		Set<Point> vertices = getVerticesSet();
		return vertices.equals(other.getVerticesSet());
	}

	/**
	 * Returns all the edges of the of this triangle.<br>
	 * 
	 * @return innutable edge set
	 */
	public synchronized ImmutableSet<Edge> getEdgeSet() {
		if (edgeSet == null) {
			try {
				edgeSet = ImmutableSet.of(new Edge(a,b), new Edge(b, c),
						new Edge(c, a));
			} catch (GeometryException e) {
				// cann't happen
			}
		}
		return edgeSet;
	}
	
	/**
	 * Returns all the edges of the of this triangle in clockwize order.
	 * 
	 * @return immutable directed edge set
	 */
	public synchronized ImmutableSet<DirectedEdge> getClockwizeEdgeSet() {
		if (directedEdgeSet == null) {
			try {
				DirectedEdge ab = new DirectedEdge(a, b);
				if (ab.isRightOf(c)) {
					directedEdgeSet = ImmutableSet.of(ab, new DirectedEdge(b, c),
							new DirectedEdge(c, a));
				} else {
					directedEdgeSet = ImmutableSet.of(new DirectedEdge(a, c), new DirectedEdge(c, b),
							new DirectedEdge(b, a));
				}
			} catch (GeometryException e) {
				// cann't happen
			}
		}
		return directedEdgeSet;
	}
	
	

	/**
	 * Construct a set of the the vertices of this triangle
	 * 
	 * @return
	 */
	public synchronized Set<Point> getVerticesSet() {
		if (verticesSet == null) {
			verticesSet = ImmutableSet.of(a, b, c);
		}
		return verticesSet;
	}

	/**
	 * @return the a point
	 */
	public Point getA() {
		return a;
	}

	/**
	 * @return the b point
	 */
	public Point getB() {
		return b;
	}

	/**
	 * @return the c point
	 */
	public Point getC() {
		return c;
	}

	/* --- Protected Methods --- */

	/**
	 * Calculates the relation between the argument point and this triangle.<br>
	 * 
	 * This method calculates the plane corresponds to this triangle (defined by
	 * the two vectors v0=b-a and v1=c-a) and calculates u and u such that: p-a
	 * = u*v0 + v*v1<br>
	 * According to the values of u and v, the relation between the point and
	 * this triangle can be defined.
	 * 
	 * @param p
	 *            The point to calculate the relation for
	 * @return the {@link PointToTriangleRelation}
	 */
	protected PointToTriangleRelation getRealtion(Point p) {
		if (p.equals(a) || p.equals(b) || p.equals(c)) {
			return PointToTriangleRelation.VERTEX;
		} else {
			// Calculate the relevant vectors
			Vector v0 = Vector.createVector(a, b); // ab
			Vector v1 = Vector.createVector(a, c); // ac
			Vector v2 = Vector.createVector(a, p); // ap

			// Calculate the dot products relevant to the equation
			double dot00 = Point.dot(v0, v0);
			double dot01 = Point.dot(v0, v1);
			double dot02 = Point.dot(v0, v2);
			double dot11 = Point.dot(v1, v1);
			double dot12 = Point.dot(v1, v2);

			// Solve the equation
			double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
			double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
			double v = (dot00 * dot12 - dot01 * dot02) * invDenom;

			// Calculates the relation
			return calculateRelation(u, v);
		}
	}

	/* --- Private Methods --- */
	
	/**
	 * @return the circumcenter of this triangle
	 */
	private Point getCircumCenter() {
		double cx = c.x;
		double cy = c.y;
		double ax = a.x - cx;
		double ay = a.y - cy;
		double bx = b.x - cx;
		double by = b.y - cy;
		
		double denom = 2 * JdtUtil.det(ax, ay, bx, by);
		double numx = JdtUtil.det(ay, ax * ax + ay * ay, by, bx * bx + by
				* by);
		double numy = JdtUtil.det(ax, ax * ax + ay * ay, bx, bx * bx + by
				* by);
		
		double ccx = cx - numx / denom;
		double ccy = cy + numy / denom;
		
		Point center = new Point(ccx, ccy);
		return center;
	}

	/**
	 * Defines the end point of the vector u*AB + v*AC
	 * 
	 * @param u
	 *            The coefficient of the AB vector
	 * @param v
	 *            The coefficient of the AC vector
	 * @return
	 */
	private PointToTriangleRelation calculateRelation(double u, double v) {
		if (u < 0 || v < 0 || u > 1 || v > 1 || (u + v > 1 + JdtUtil.PERCISION)) {
			return PointToTriangleRelation.OUTSIDE;
		} else if (u == 0) {
			return PointToTriangleRelation.ON_AC;
		} else if (v == 0) {
			return PointToTriangleRelation.ON_AB;
		} else if (Math.abs(1 - (u + v)) < JdtUtil.PERCISION) {
			return PointToTriangleRelation.ON_BC;
		} else {
			return PointToTriangleRelation.INSIDE;
		}
	}

	/* --- Inner classes --- */

	/**
	 * An enum which represents all the possible relations between a point and a
	 * triangle
	 * 
	 * @author Shay
	 */
	public static enum PointToTriangleRelation {
		VERTEX, OUTSIDE, INSIDE, ON_AB, ON_AC, ON_BC,
	}
}
